package leetcode.code1278;

import java.util.Iterator;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int palindromePartition(String s, int k) {
		int n = s.length();
		int[][] lr = new int[n][n];
		char[] cs = s.toCharArray();
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				int l = i, r = j;
				int sum = 0;
				while (l < r) {
					if (cs[l] != cs[r]) {
						sum++;
					}
					l++;
					r--;
				}
				lr[i][j] = sum;
			}
		}
		int[][] dp = new int[n][k];
		for (int i = 0; i < n; i++) {
			dp[i][0] = lr[0][i];
		}
		for (int K = 1; K < k; K++) {
			for (int i = 0; i < n; i++) {
				dp[i][K] = n + 1;
				for (int j = 0; j < i; j++) {
					dp[i][K] = Math.min(dp[i][K], dp[j][K - 1] + lr[j + 1][i]);
				}
			}
		}
		return dp[n - 1][k - 1];
	}

	@Override
	public void debug4() {
		H.compare(1, this.palindromePartition("abc", 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
